package com.acwing.lc.part1;

import java.util.Stack;

/**
 * @author rkc
 * @date 2022/9/13 10:37
 */
public class LC42接雨水 {

    private Stack<Integer> stk = new Stack<>();

    public int trap(int[] height) {
        int ans = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stk.isEmpty() && height[stk.peek()] < height[i]) {
                int top = stk.pop();
                if (stk.isEmpty()) break;
                ans += (i - stk.peek() - 1) * (Math.min(height[i], height[stk.peek()]) - height[top]);
            }
            stk.push(i);
        }
        return ans;
    }
}
